import java.util.*;

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Node {
    int val;
    Node next;
    Node random;
    public Node left;
    public Node right;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}


public class Demo2 {

    //905. 按奇偶排序数组
    public int[] sortArrayByParity(int[] nums) {
        int left = -1, right = nums.length, cur = 0;
        while(cur < right) {
            if(nums[cur] == 0) cur++;
            else if(nums[cur] % 2 == 0) swap(nums, ++left, cur++);
            else swap(nums, cur, --right);
        }
        return nums;
    }
    public void swap(int[] nums, int x, int y) {
        int tmp = nums[x];
        nums[x] = nums[y];
        nums[y] = tmp;
    }


    //LCR 021. 删除链表的倒数第 N 个结点
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode fast = head;
        while(n-- > 0) fast = fast.next;
        ListNode newHead = new ListNode();
        newHead.next = head;
        ListNode t = newHead;
        while(fast != null) {
            t = head;
            head = head.next;
            fast = fast.next;
        }
        t.next = head.next;
        return newHead.next;
    }


    //LCR 022. 环形链表 II
    public ListNode detectCycle(ListNode head) {
        if(head == null) return null;

        ListNode slow = head, fast = head;
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if(fast == slow) break;
        }
        if(fast == null || fast.next == null) return null;

        fast = head;
        while(fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }


    //LCR 024. 反转链表
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) return head;
        // 头插法
        ListNode newHead = null;
        while(head != null) {
            ListNode next = head.next;
            head.next = newHead;
            newHead = head;
            head = next;
        }
        return newHead;
    }


    //21. 合并两个有序链表
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1 == null) return list2;
        if(list2 == null) return list1;

        ListNode newHead = new ListNode();
        ListNode t = newHead;
        while(list1 != null && list2 != null) {
            if(list1.val <= list2.val) {
                t.next = list1;
                list1 = list1.next;
            } else {
                t.next = list2;
                list2 = list2.next;
            }
            t = t.next;
        }
        if(list1 != null) t.next = list1;
        if(list2 != null) t.next = list2;
        return newHead.next;
    }


    //572. 另一棵树的子树
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(isSameTree(root, subRoot)) return true;

        if(root == null) return false;

        return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
    }
    private boolean isSameTree(TreeNode root, TreeNode subRoot) {
        if(root == null && subRoot == null) return true;
        if(root == null || subRoot == null) return false;
        if(root.val != subRoot.val) return false;

        return isSameTree(root.left, subRoot.left) && isSameTree(root.right, subRoot.right);
    }


    //LCR 144. 翻转二叉树
    public TreeNode mirrorTree(TreeNode root) {
        if(root == null) return null;
        TreeNode leftTree = root.left;      // 先保存左子树或右子树，防止下面的操作出现错误
        root.left = mirrorTree(root.right);
        root.right = mirrorTree(leftTree);
        return root;
    }


    //LCR 145. 判断对称二叉树
    public boolean checkSymmetricTree(TreeNode root) {
        if(root == null) return true;
        return childIsSymmetric(root.left, root.right);
    }
    public boolean childIsSymmetric(TreeNode leftTree, TreeNode rightTree) {
        if(leftTree == null && rightTree == null) return true;
        if(leftTree == null || rightTree == null) return false;

        if(leftTree.val != rightTree.val) return false;
        return childIsSymmetric(leftTree.left, rightTree.right) && childIsSymmetric(leftTree.right, rightTree.left);
    }




    //54. 螺旋矩阵
    ArrayList<Integer> ret;
    public List<Integer> spiralOrder(int[][] matrix) {
        ret = new ArrayList<>();
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return ret;
        int i = 0, j = 0, m = matrix.length, n = matrix[0].length;

        while(ret.size() < m * n) {
            search(matrix, i, j, m - i - 1, n - j - 1);
            i++; j++;
        }
        return ret;
    }

    private void search(int[][] arr, int x, int y, int row, int col) {
        // 往右遍历
        for(int j = y; j <= col; j++) ret.add(arr[x][j]);
        // 向下遍历
        for(int i = x + 1; i <= row; i++) ret.add(arr[i][col]);

        if(x == row || y == col) return;
        // 向左遍历
        for(int j = col - 1; j >= y; j--) ret.add(arr[row][j]);
        // 向上遍历
        for(int i = row - 1; i > x; i--) ret.add(arr[i][y]);
    }



    //155. 最小栈
    class MinStack {
        Deque<Integer> t1;
        Deque<Integer> t2;

        public MinStack() {
            t1 = new ArrayDeque<>();
            t2 = new ArrayDeque<>();
        }

        public void push(int val) {
            t1.push(val);
            if(t2.isEmpty() || val <= t2.peek()) {
                t2.push(val);
            }
        }

        public void pop() {
            int val = t1.pop();
            if(val == t2.peek()) {
                t2.pop();
            }
        }

        public int top() {
            return t1.peek();
        }

        public int getMin() {
            return t2.peek();
        }
    }


    //946. 验证栈序列
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Deque<Integer> stack = new ArrayDeque<>();
        int i = 0;
        for(int x : pushed) {
            stack.push(x);
            while(!stack.isEmpty() && popped[i] == stack.peek()) {
                stack.pop();
                i++;
            }
        }
        return i == popped.length;
    }


    //102. 二叉树的层序遍历
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if(root == null) return ret;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);

        while(!q.isEmpty()) {
            int sz = q.size();
            List<Integer> tmp = new ArrayList<>();
            while(sz-- > 0) {
                TreeNode node = q.poll();
                tmp.add(node.val);
                if(node.left != null) q.offer(node.left);
                if(node.right != null) q.offer(node.right);
            }
            ret.add(tmp);
        }
        return ret;
    }


    //107. 二叉树的层序遍历 II
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if(root == null) return ret;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);

        while(!q.isEmpty()) {
            int sz = q.size();
            List<Integer> tmp = new ArrayList<>();
            while(sz-- > 0) {
                TreeNode node = q.poll();
                tmp.add(node.val);
                if(node.left != null) q.offer(node.left);
                if(node.right != null) q.offer(node.right);
            }
            ret.add(tmp);
        }
        Collections.reverse(ret);
        return ret;
    }



    //LCR 152. 验证二叉搜索树的后序遍历序列
    public boolean verifyTreeOrder(int[] postorder) {
        return checkTreeOrder(postorder, 0, postorder.length - 1);
    }
    public boolean checkTreeOrder(int[] postorder, int left, int right) {
        if(left >= right) return true;

        int rootVal = postorder[right], cur = left;
        while(cur < right && postorder[cur] < rootVal) cur++;
        for(int i = cur; i < right; i++) {
            if(postorder[i] < rootVal) return false;
        }

        return checkTreeOrder(postorder, left, cur - 1) && checkTreeOrder(postorder, cur, right - 1);
    }



    //331. 验证二叉树的前序序列化
    public boolean isValidSerialization(String _preorder) {
        Deque<Integer> st = new ArrayDeque<>();
        char[] preorder = _preorder.toCharArray();
        int cur = 0;
        while(cur < preorder.length) {
            if(preorder[cur] == ',') cur++;
            else if(preorder[cur] == '#') {
                if(st.isEmpty()) break;
                st.pop();
                cur++;
            } else {
                int tmp = 0;
                while(cur < preorder.length && preorder[cur] != ',') {
                    tmp = tmp * 10 + preorder[cur++] - '0';
                }
                st.push(tmp);
            }
        }
        return cur == preorder.length - 1;
    }


    //112. 路径总和
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root == null) return false;
        targetSum -= root.val;

        if(root.left == null && root.right == null && targetSum == 0) return true;
        return hasPathSum(root.left, targetSum) || hasPathSum(root.right, targetSum);
    }


    //LCR 154. 复杂链表的复制
    public Node copyRandomList(Node head) {
        if(head == null) return null;
        Node cur = head;
        Map<Node, Node> hash = new HashMap<>();
        while(cur != null) {
            hash.put(cur, new Node(cur.val));
            cur = cur.next;
        }
        for(cur = head; cur != null; cur = cur.next) {
            hash.get(cur).next = hash.get(cur.next);
            hash.get(cur).random = hash.get(cur.random);
        }
        return hash.get(head);

    }


    //LCR 155. 将二叉搜索树转化为排序的双向链表
    Node prev, head;
    public Node treeToDoublyList(Node root) {
        if(root == null) return null;

        dfs(root);
        prev.right = head;
        head.left = prev;
        return head;
    }
    private void dfs(Node root) {
        if(root == null) return;
        dfs(root.left);
        if(head == null) head = root;
        if(prev == null) {
            prev = root;
        } else {
            prev.right = root;
            root.left = prev;
            prev = root;
        }
        dfs(root.right);
    }



    //46. 全排列
    List<List<Integer>> ret2;
    List<Integer> path2;
    boolean[] vis;

    public List<List<Integer>> permute(int[] nums) {
        ret = new ArrayList<>();
        path2 = new ArrayList<>();
        vis = new boolean[nums.length];

        dfs(nums);
        return ret2;
    }
    private void dfs(int[] nums) {
        if(path2.size() == nums.length) {
            ret2.add(new ArrayList<>(path2));
            return;
        }

        for(int i = 0; i < nums.length; i++) {
            if(!vis[i]) {
                vis[i] = true;
                path2.add(nums[i]);
                dfs(nums);
                vis[i] = false;
                path2.remove(path2.size() - 1);
            }
        }
    }



    //47. 全排列 II
    List<List<Integer>> ret3;
    List<Integer> path3;
    boolean[] vis3;

    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        ret = new ArrayList<>();
        path3 = new ArrayList<>();
        vis = new boolean[nums.length];

        dfs2(nums);
        return ret3;
    }
    private void dfs2(int[] nums) {
        if(path3.size() == nums.length) {
            ret3.add(new ArrayList<>(path3));
            return;
        }

        for(int i = 0; i < nums.length; i++) {
            if(!vis[i] && (i == 0 || nums[i] != nums[i - 1] || vis[i - 1])) {
                vis[i] = true;
                path3.add(nums[i]);
                dfs2(nums);
                vis[i] = false;
                path3.remove(path3.size() - 1);
            }
        }
    }



    //169. 多数元素
    public int majorityElement(int[] nums) {
        int key = 0, count = 0;
        for(int x : nums) {
            if(count == 0) key = x;
            if(x == key) count++;
            else count--;
        }
        if(count > 0) {
            count = 0;
            for(int x : nums)
                if(x == key) count++;
        }
        if(count > nums.length / 2) return key;
        return -1;
    }



    //229. 多数元素 II
    public List<Integer> majorityElement2(int[] nums) {
        List<Integer> ret = new ArrayList<>();
        int n = nums.length;
        int key1 = nums[0], key2 = n > 1 ? nums[1] : 0, count1 = 0, count2 = 0;
        for(int x : nums) {
            if(x == key1) count1++;
            else if(x == key2) count2++;
            else {
                if(count1 == 0) {
                    key1 = x;
                    count1 = 1;
                    continue;
                }
                if(count2 == 0) {
                    key2 = x;
                    count2 = 1;
                    continue;
                }
                count1--;
                count2--;
            }
        }

        count1 = count2 = 0;
        for(int x : nums) {
            if(x == key1) count1++;
            else if(x == key2) count2++;
        }
        if(count1 > nums.length / 3) ret.add(key1);
        if(count2 > nums.length / 3) ret.add(key2);
        return ret;
    }



    //215. 数组中的第K个最大元素
    public int findKthLargest(int[] nums, int k) {
        // 快速选择算法
        return quickSelect(nums, 0, nums.length - 1, k);
    }
    private int quickSelect(int[] nums, int l, int r, int k) {
        if(l >= r) return nums[l];
        int left = l - 1, right = r + 1, cur = l;
        int key = nums[l + new Random().nextInt(r - l + 1)];

        while(cur < right) {
            if(nums[cur] < key) swap(nums, ++left, cur++);
            else if(nums[cur] > key) swap(nums, --right, cur);
            else cur++;
        }

        // 此时val < key:[l,left]   val == key:[left+1,right-1]   val > key:[right,r]
        int c = r - right + 1, b = right - left - 1;
        if(r - right + 1 >= k) return quickSelect(nums, right, r, k);
        else if(r - left >= k) return key;
        else return quickSelect(nums, l, left, k - r + left);
    }
//    private void swap(int[] nums, int x, int y) {
//        int tmp = nums[x];
//        nums[x] = nums[y];
//        nums[y] = tmp;
//    }




    //面试题 17.14. 最小K个数
    public int[] smallestK(int[] arr, int k) {
        qsort(arr, 0, arr.length - 1, k);
        int[] ret = new int[k];
        for(int i = 0; i < k; i++) ret[i] = arr[i];
        return ret;
    }
    private void qsort(int[] arr, int l, int r, int k) {
        if(l >= r) return;
        int key = arr[l + new Random().nextInt(r - l + 1)];
        int left = l - 1, right = r + 1, cur = l;

        while(cur < right) {
            if(arr[cur] < key) swap(arr, ++left, cur++);
            else if(arr[cur] == key) cur++;
            else swap(arr, --right, cur);
        }
        int a = left - l + 1, b = cur - left - 1;
        if(a > k) qsort(arr, l, left, k);
        else if(a + b >= k) return;
        else qsort(arr, right, r, k - a - b);
    }
//    private void swap(int[] arr, int x, int y) {
//        int tmp = arr[x];
//        arr[x] = arr[y];
//        arr[y] = tmp;
//    }



    //295. 数据流的中位数
    class MedianFinder {
        PriorityQueue<Integer> maxHeap;     // 存储前半部分的较小元素
        PriorityQueue<Integer> minHeap;     // 存储后半部分的较大元素

        public MedianFinder() {
            maxHeap = new PriorityQueue<>((o1, o2) -> o2 - o1);
            minHeap = new PriorityQueue<>((o1, o2) -> o1 - o2);
        }

        public void addNum(int num) {
            if(maxHeap.size() == minHeap.size()) {
                if(maxHeap.isEmpty() || num < maxHeap.peek()) {
                    maxHeap.add(num);
                } else {
                    minHeap.add(num);
                    maxHeap.add(minHeap.poll());
                }
            } else {
                // 把元素加入小根堆
                if(num < maxHeap.peek()) {
                    minHeap.add(maxHeap.poll());
                    maxHeap.add(num);
                }else {
                    minHeap.add(num);
                }
            }
        }

        public double findMedian() {
            if(maxHeap.size() == minHeap.size()) return (maxHeap.peek() + minHeap.peek()) / 2.0;
            else return (double)maxHeap.peek();
        }
    }



    //53. 最大子数组和
    public int maxSubArray(int[] nums) {
        // dp[i]: 以 i 位置为结尾的所有子数组中的最大和
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = nums[0];

        int ret = dp[0];
        for(int i = 1; i < n; i++) {
            dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
            ret = Math.max(ret, dp[i]);
        }
        return ret;
    }



    //179. 最大数
    public String largestNumber(int[] nums) {
        int n = nums.length;
        String[] strs = new String[n];
        for(int i = 0; i < n; i++) strs[i] = String.valueOf(nums[i]);
        Arrays.sort(strs, (o1, o2) -> {
            return (o2 + o1).compareTo(o1 + o2);
        });

        StringBuilder ret = new StringBuilder();
        for(String s : strs) ret.append(s);
        if(ret.charAt(0) == '0') return "0";
        return ret.toString();
    }


    //91. 解码方法
    public int numDecodings(String s) {
        // 状态表示: dp[i] 表示为 i 位置为结尾时，解码方法的总数
        // 若 i 位置单独解码时，解码成功 -> 有dp[i-1]种方法
        // 若 i 和 i-1 位置联合解码时，解码成功 -> 有dp[i-2]种方法
        // 因此 dp[i] = dp[i-1] + dp[i-2]

        // 1. 创建 dp 表
        int n = s.length();
        int[] dp = new int[n];
        char[] arr = s.toCharArray();
        // 2. 初始化 dp[0] 和 dp[1]
        if(arr[0] != '0') dp[0] = 1;
        if(n == 1) return dp[0];

        int a = arr[0] - '0', b = arr[1] - '0';     // a 前一个数字， b表示后面一个数字
        if(a >= 1 && a <= 9 && b >= 1 && b <= 9) dp[1]++;
        if(a * 10 + b >= 10 && a * 10 + b <= 26) dp[1]++;
        // 3. 进行填表
        for(int i = 2; i < n; i++) {
            a = arr[i-1] - '0'; b = arr[i] - '0';
            if(b >= 1 && b <= 9) dp[i] += dp[i-1];
            if(a * 10 + b >= 10 && a * 10 + b <= 26) dp[i] += dp[i-2];
        }
        // 4. 返回结果
        return dp[n-1];
    }


    //639. 解码方法 II
    public int numDecodings2(String _s) {
        long MOD = (long)(1e9 + 7);

        int n = _s.length();
        char[] s = (" " + _s).toCharArray();
        long a = 1, b = 0;
        if(s[1] == '*') b = 9;
        else if(s[1] != '0') b++;

        long c = b;
        for(int i = 2; i <= n; i++) {
            c = check1digit(s[i]) * b % MOD;
            c = (c + check2digits(s[i - 1], s[i]) * a) % MOD;
            a = b; b = c;
        }
        return (int)c;
    }
    private int check1digit(char ch) {                      // 单独解码
        if(ch >= '1' && ch <= '9') return 1;                // ch为数字
        else if(ch == '*') return 9;                        // ch 为*
        return 0;
    }
    private int check2digits(char ch1, char ch2) {
        if(ch2 != '*') {                                    // ch2 为数字
            if(ch1 != '*') {                                // ch1 为数字
                int sum = (ch1 - '0') * 10 + ch2 - '0';
                if(sum >= 10 && sum <= 26) return 1;
            } else {                                        // ch1 为 *
                if(ch2 >= '7' && ch2 <= '9') return 1;
                else return 2;
            }
        } else {                                            // ch2 为*
            if(ch1 == '1') return 9;
            else if(ch1 == '2') return 6;
            else if(ch1 == '*') return 15;
        }
        return 0;
    }



    //LCR 166. 珠宝的最高价值
    public int jewelleryValue(int[][] frame) {
        // 1. 创建 dp 表
        // 2. 初始化
        // 3. 填表
        // 4. 返回值
        int m = frame.length, n = frame[0].length;
        int[][] dp = new int[m + 1][n + 1];
        for(int i = 1; i <= m; i++)
            for(int j = 1; j <= n; j++)
                dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]) + frame[i - 1][j - 1];
        return dp[m][n];
    }


    //3. 无重复字符的最长子串
    public int lengthOfLongestSubstring(String _s) {
        int[] hash = new int[128];
        char[] s = _s.toCharArray();
        int left = 0, right = 0, ret = 0;

        while(right < s.length) {
            hash[s[right]]++;

            while(hash[s[right]] > 1) {
                hash[s[left++]]--;
            }
            ret = Math.max(ret, right - left + 1);
            right++;
        }
        return ret;

    }


    //387. 字符串中的第一个唯一字符
    public int firstUniqChar(String s) {
        int[] count = new int[26];
        for(int i = 0; i < s.length(); i++) {
            count[s.charAt(i) - 'a']++;
        }
        for(int i = 0; i < s.length(); i++) {
            if(count[s.charAt(i) - 'a'] == 1) return i;
        }
        return -1;
    }
}
